// https://leetcode.cn/problems/count-and-say/description/

// 算法思路总结：
// 1. 模拟外观数列的生成过程
// 2. 从"1"开始，迭代生成第n项
// 3. 双指针统计连续相同字符的出现次数
// 4. 将"计数+字符"拼接成新的描述字符串
// 5. 时间复杂度：O(2ⁿ)，空间复杂度：O(2ⁿ)

#include <iostream>
using namespace std;

#include <vector>
#include <string>
#include <algorithm>

class Solution 
{
public:
    string countAndSay(int n)
    {
        if (n == 1) return "1";

        string res = "1";
        for (int i = 1 ; i < n ; i++)
        {
            string tmp;
            for (int l = 0, r = 0 ; r < res.size() ; )
            {
                int count = 0;
                while (res[r] == res[l])
                {
                    count++;
                    r++;
                }
                tmp += to_string(count) + res[l];
                l = r;
            }
            res = tmp;
        }

        return res;
    }
};

int main()
{
    Solution sol;
    int n1 = 4, n2 = 1;

    cout << sol.countAndSay(n1) << endl;
    cout << sol.countAndSay(n2) << endl;

    return 0;
}